package main

import "sort"

//给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
//
// 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
//
//
//
// 示例 1:
//
//
//输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
//
// 示例 2:
//
//
//输入: strs = [""]
//输出: [[""]]
//
//
// 示例 3:
//
//
//输入: strs = ["a"]
//输出: [["a"]]
//
//
//
// 提示：
//
//
// 1 <= strs.length <= 10⁴
// 0 <= strs[i].length <= 100
// strs[i] 仅包含小写字母
//
// Related Topics 哈希表 字符串 排序 👍 1052 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
func groupAnagrams(strs []string) (ans [][]string) {
	strMap := make(map[string][]int)
	for i, str := range strs {
		t := runeSlice(str)
		sort.Sort(t)
		if v, ok := strMap[string(t)]; ok {
			v = append(v, i)
			strMap[string(t)] = v
		} else {
			strMap[string(t)] = []int{i}
		}
	}
	for _, value := range strMap {
		var an []string
		for _, index := range value {
			an = append(an, strs[index])
		}
		ans = append(ans, an)
	}

	return
}

type runeSlice []rune

func (x runeSlice) Len() int           { return len(x) }
func (x runeSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x runeSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

//leetcode submit region end(Prohibit modification and deletion)
